{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.5 Simon's Algorithm\n",
    "\n",
    "* [Q# exercise: Grover's algorithm](./2-Quantum_Algorithms/5-Simon_s_Algorithm.ipynb#qex)\n",
    "\n",
    "Simon's algorithm was conceived by Daniel Simon in 1994. The problem it solves is a specific one that does not have any known practical value, but the quantum algorithm solution is exponentially faster than any known classical solution. Simon's problem is this: There is a black box function with input $x$ and output function $f(x)$, and there are values of $x$ that give the same $f(x)$. This happens specifically according to a value $s$ such that the value of $f(x)$ is the same for $x$ and $x \\oplus s$. That is, when $\\textit{s}$ is not 0, two inputs corresponding to any one given output have bitwise XOR equal to $s$. When $s$ is zero, the inputs\n",
    "correspond to unique outputs. Find the value $s$. Although Simon's algorithm by itself has little practical\n",
    "value, it inspired future development for the Shor's algorithm in the next session.\n",
    "\n",
    "<center>\n",
    "Let's say we are given a black box that implements the following function:\n",
    "\n",
    "<table style=\"width: 200px; border: 1px solid black; text-align: center;\">\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <th style=\"border: 1px solid black;\">$x$</th>\n",
    "        <th style=\"border: 1px solid black;\">$y=f(x)$</th>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0000</td>\n",
    "        <td style=\"border: 1px solid black;\">0000</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0001</td>\n",
    "        <td style=\"border: 1px solid black;\">0001</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0010</td>\n",
    "        <td style=\"border: 1px solid black;\">0010</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0011</td>\n",
    "        <td style=\"border: 1px solid black;\">0011</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0100</td>\n",
    "        <td style=\"border: 1px solid black;\">0100</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0101</td>\n",
    "        <td style=\"border: 1px solid black;\">0101</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0110</td>\n",
    "        <td style=\"border: 1px solid black;\">0110</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0111</td>\n",
    "        <td style=\"border: 1px solid black;\">0111</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1000</td>\n",
    "        <td style=\"border: 1px solid black;\">0010</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1001</td>\n",
    "        <td style=\"border: 1px solid black;\">0011</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1010</td>\n",
    "        <td style=\"border: 1px solid black;\">0000</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1011</td>\n",
    "        <td style=\"border: 1px solid black;\">0001</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1100</td>\n",
    "        <td style=\"border: 1px solid black;\">0110</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1101</td>\n",
    "        <td style=\"border: 1px solid black;\">0111</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1110</td>\n",
    "        <td style=\"border: 1px solid black;\">0100</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1111</td>\n",
    "        <td style=\"border: 1px solid black;\">0101</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "$Table 2.5.1$\n",
    "\n",
    "</center>\n",
    "\n",
    "As one can see, it is a 2-to-1 function (that is, two inputs map to the same output). The value of $y$ is the same for $x$ and $x\\oplus s$ (here $s$ = 1010). Since it's a black box, we don't know the contents of this table and\n",
    "value of $s$ beforehand; but we are free to execute this black box any number of times for different inputs and check the outputs. Now, the problem is to identify the value of $s$. The direct way to solve this problem is to start executing the black box with inputs 0000, 0001 and so on and the moment we see a repeated output, we can do an $\\oplus$ between the input strings that gave the same output and we will get the answer.\n",
    "In this example, if we start from the beginning, the first repeated output is 0010 and from the inputs 0010 and 1000. We can calculate $\\textit{s}$ = 0010 $\\oplus$ 1000 = 1010. You can check that, for every $\\textit{x}$, the output will be the same as that of the input $\\textit{x}\\oplus\\textit{s}$ ($\\textit{s}$ = 1010 in this example).\n",
    "\n",
    "However, if we tried executing the black box for all the inputs and we didn't get any repeated\n",
    "outputs, it means that the black box that was given was a 1-to-1 function and $s$ = 0000. The table looks\n",
    "as follows:\n",
    "\n",
    "<center>\n",
    "\n",
    "<table style=\"width: 200px; border: 1px solid black; text-align: center; padding: 25px 50px 75px 100px;\">\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <th style=\"border: 1px solid black;\">$x$</th>\n",
    "        <th style=\"border: 1px solid black;\">$y=f(x)$</th>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0000</td>\n",
    "        <td style=\"border: 1px solid black;\">0000</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0001</td>\n",
    "        <td style=\"border: 1px solid black;\">0001</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0010</td>\n",
    "        <td style=\"border: 1px solid black;\">0010</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0011</td>\n",
    "        <td style=\"border: 1px solid black;\">0011</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0100</td>\n",
    "        <td style=\"border: 1px solid black;\">0100</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0101</td>\n",
    "        <td style=\"border: 1px solid black;\">0101</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0110</td>\n",
    "        <td style=\"border: 1px solid black;\">0110</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">0111</td>\n",
    "        <td style=\"border: 1px solid black;\">0111</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1000</td>\n",
    "        <td style=\"border: 1px solid black;\">1000</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1001</td>\n",
    "        <td style=\"border: 1px solid black;\">1001</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1010</td>\n",
    "        <td style=\"border: 1px solid black;\">1010</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1011</td>\n",
    "        <td style=\"border: 1px solid black;\">1011</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1100</td>\n",
    "        <td style=\"border: 1px solid black;\">1100</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1101</td>\n",
    "        <td style=\"border: 1px solid black;\">1101</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1110</td>\n",
    "        <td style=\"border: 1px solid black;\">1110</td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1111</td>\n",
    "        <td style=\"border: 1px solid black;\">1111</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "$Table 2.5.2$\n",
    "\n",
    "</center>\n",
    "\n",
    "\n",
    "In this example, we have $y = f(x) = x$; this needs not be the case always. we can have $x$ = 0000 for a different combination of inputs and outputs so long as there are no repetitions, i.e. for any 1-to-1 function.\n",
    "\n",
    "Given any such 1-to-1 or 2-to-1 black box, we need to at maximum execute the given black box for at most once more than half of the total number of possible input combinations to get a repetition. The upper bound complexity will be trivially $0(2^n)$. If we don't get a repetition even after that, we can safely assume that $s$ = 0000. Also, in the best-case scenario we might get a repetition just after two iterations.\n",
    "\n",
    "Let's consider a case where we are not that lucky. If $n$, is the number of bits, then the total number of possible values of $s$ will be $2^n$. Let's say we execute the black box four times for the first four inputs, e.g. the black box for 0000, 0001, 0010, 0011, and we don't find any repeated outputs. This means $s$ is not an $\\oplus$ between any 2 of these inputs. How many ways can we choose two values out of four? The answer is $C_2^4$. This is a common formula in Permutations and Combinations, and you can find the proof\n",
    "easily online. Following are the 6 possible combinations arising form 4 inputs:\n",
    "\n",
    "<center>\n",
    "0000 $\\oplus$ 0001 = 0001\n",
    "\n",
    "0000 $\\oplus$ 0010 = 0010\n",
    "\n",
    "0000 $\\oplus$ 0011 = 0011\n",
    "\n",
    "0001 $\\oplus$ 0010 = 0011\n",
    "\n",
    "0001 $\\oplus$ 0011 = 0010\n",
    "\n",
    "0010 $\\oplus$ 0011 = 0001\n",
    "</center>\n",
    "\n",
    "As you can see, there are some repetitions. So the number $C_2^4$ will only give us the upper bound of the number of eliminated possibilities rather than the exact number. Now, let's say $q$ is the number of queries needed to cover 2$^n$ possible values of $s$, then the following condition will be true:\n",
    "\n",
    "<center>\n",
    "$C_2^q \\geq $2$^n$,\n",
    "</center>\n",
    "\n",
    "which can be expanded as\n",
    "\n",
    "<center>\n",
    "$\\frac{q(q-1)}{2}\\geq $2$^n$,\n",
    "</center>\n",
    "\n",
    "which can be written as\n",
    "\n",
    "<center>\n",
    "$q\\gtrsim$2$^{n/2}$.\n",
    "</center>\n",
    "\n",
    "Remember that this is $\\Omega($2$^{n/2})$, not $0($2$^{n/2})$, the best-case scenario (but it is not exactly the best case, as\n",
    "the best case needs only 2 iterations; here we are calculating the lower-bound to eliminate all possible\n",
    "values of $s$ to gain some further insight on the complexity). So, this is the lower bound complexity rather\n",
    "than the upper bound complexity.\n",
    "\n",
    "<div style=\"background-color:#E1DFDD; width:95%\">\n",
    "<center>\n",
    "Math insert $-$ complexity evaluation ---------------------------------------------------\n",
    "</center>\n",
    "\n",
    "Now, to gain some further insights, let's try to calculate the complexity using probability. We will try to find the probability of getting a repetition at the $k^{th}$ iteration. Since we are looking for repetitions, we are considering the case when $s \\neq$ 0000. So, the initial total number of possible values for $s$ will be 2$^n$ $-$ 1.\n",
    "\n",
    "We will use the following colored cells to visually represent the lists and indicate which entry we are talking with the color code. After completing $k$ $-$ 1 iterations, we must have eliminated at most ($k$ $-$ 1)($k$ $-$ 2)/2 possible values of $s$ ( as deducted above in the previous paragraphs):\n",
    "\n",
    "<center>\n",
    "<table  style=\"width: 90%; border: 1px solid black; text-align: center;\">\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <th style=\"border: 1px solid black; text-align: center;\">$\\textbf{x}$ (Black box evaluated for $k$ $-$ 1 values of $x$; $k -$ 1 $red$ $boxes$)</th>\n",
    "        <th style=\"border: 1px solid black; text-align: center;\">$\\textbf{Eliminated}$ $ \\textbf{possibilities}$ $ \\textbf{for}$ $ \\textbf{s}$ (after $k$ $-$ 1 iterations; at most ($k$ $-$ 1)($k$ $-$ 2)/2; marked in brown boxes)</th>\n",
    "        <th style=\"border: 1px solid black; text-align: center;\">Left over possibilities for 2$^n -$ 1 $-$ ($k$ $-$ 1)($k$ $-$ 2)/2; marked in green)</th>\n",
    "        <th style=\"border: 1px solid black;\"></th>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black; background-color:#E13E1C\">0000...000</td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\">0000...000</td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black; background-color:#E13E1C\">0000...001</td>\n",
    "        <td style=\"border: 1px solid black;\">0000...001</td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black; background-color:#E13E1C\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black;\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black; background-color:#E13E1C\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#FFFB0C\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#4DC0DF\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">...</td>\n",
    "        <td style=\"border: 1px solid black;\">...</td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black;\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black;\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black;\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black;\"> </td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black;\"> </td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "        <td style=\"border: 1px solid black; background-color:#81D35B\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "    </tr>\n",
    "    <tr style=\"border: 1px solid black;\">\n",
    "        <td style=\"border: 1px solid black;\">1111...111</td>\n",
    "        <td  style=\"border: 1px solid black; background-color:#EDBB99\">1111...111</td>\n",
    "        <td  style=\"border: 1px solid black; background-color:#EDBB99\"></td>\n",
    "        <td style=\"border: 1px solid black;\"></td>\n",
    "    </tr>\n",
    "</table>\n",
    "</center>\n",
    "\n",
    "Since $s$ can have 2$^n$ $-$ 1 total possible values, and because after $k$ $-$ 1 iterations we have eliminated at most ($k$ $-$ 1)($k$ $-$ 2)/2 possible values, the remaining possible values will be at least:\n",
    "\n",
    "<center>\n",
    "2$^n$ $-$ 1 $-$ ($k$ $-$ 1)($k$ $-$ 2)/2.\n",
    "</center>\n",
    "\n",
    "Now, in the $k^{th}$ iteration (evaluating the blue cell), what is the probability that the output will be the same as the box marked in yellow? It will be at most:\n",
    "\n",
    "<center>\n",
    "$\\frac{1}{2^n - 1 - (k - 1)(k - 2)/2}$\n",
    "</center>\n",
    "\n",
    "Because, out of the green ones (remaining possibilities for $s$), at least one will be the same as the yellow one. So, the above equation calculates the probability that the blue cell repeats the yellow cell.\n",
    "\n",
    "Now, what is the probability that there is a repetition with one of the red cells? It will be at most (simple probability addition rule; add the above probability $k$ $-$ 1 times):\n",
    "\n",
    "<center>\n",
    "$\\frac{k-1}{2^n - 1 - (k - 1)(k - 2)/2}$.\n",
    "</center>\n",
    "\n",
    "And calculating the upper bound of the above expression by ignoring the lower order terms gives:\n",
    "\n",
    "<center>\n",
    "$\\frac{k-1}{2^n - 1 - (k - 1)(k - 2)/2} \\leq \\frac{2k}{2^{n+1}-k^2}$.\n",
    "</center>\n",
    "\n",
    "This is the probability of getting a repetition on the í‘˜í‘˜í‘¡í‘¡â„Ž iteration. Now, let's say we have\n",
    "executed í¼í¼ iterations, this is the probability that we get a repetition for at least one of these\n",
    "iterations:\n",
    "\n",
    "<center>\n",
    "$\\sum_{k=1}^m\\frac{2k}{2^{n+1}-k^2}$\n",
    "</center>\n",
    "\n",
    "and getting the upper bound by using $m$ in all the terms:\n",
    "\n",
    "<center>\n",
    "$\\sum_{k=1}^m\\frac{2k}{2^{n+1}-k^2} \\leq \\sum_{k=1}^m\\frac{2m}{2^{n+1}-m^2}$,\n",
    "</center>\n",
    "\n",
    "getting the upper bound of the sum (hint: sum of first $m$ numbers = $m(m$ + 1)/2):\n",
    "\n",
    "<center>\n",
    "$\\sum_{k=1}^m\\frac{2m}{2^{n+1}-m^2} \\leq \\frac{2m^2}{2^{n+1}-m^2}$\n",
    "</center>\n",
    "\n",
    "\n",
    "And if you want this probability to be at least $\\frac{3}{4}$, then\n",
    "\n",
    "<center>\n",
    "$\\frac{2m^2}{2^{n+1}-m^2} \\geq \\frac{3}{4}$,\n",
    "</center>\n",
    "\n",
    "which becomes:\n",
    "\n",
    "<center>\n",
    "$m \\geq \\sqrt{\\frac{6}{11}2^n}$.\n",
    "</center>\n",
    "\n",
    "Here, we again get $m=\\Omega(2^{n/2})$. This the lower bound of iterations needed to get an answer with probability higher than $\\frac{3}{4}$. Remember that this is $\\Omega$ and not $0$.\n",
    "<hr>\n",
    "\n",
    "</div>\n",
    "\n",
    "The Simon's algorithm is represented by this circuit with $U_f$ being a black box.\n",
    "\n",
    "<img src=\"img/5-fig2.5.1.png\" style=\"width: 90%;\">\n",
    "\n",
    "<center>\n",
    "$Fig. 2.5.1$\n",
    "</center>\n",
    "<div style=\"background-color:#E1DFDD; width:95%\">\n",
    "\n",
    "<center>\n",
    "$Math$ $insert$ $-$ $test$ $Simon's$ $algorithm$ -----------------------------------------------------------\n",
    "</center>\n",
    "\n",
    "If we consider $n$ = 3, the initial state is\n",
    "\n",
    "<center>\n",
    "$|000⟩ \\otimes |000⟩$.\n",
    "</center>\n",
    "H gates are applied on the first three qubits (refer to previous algorithms):\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}\\sum_{x=0}^{2^3-1}(|x⟩ \\otimes |000⟩)$.\n",
    "</center>\n",
    "Now, apply the black box:\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}\\sum_{x=0}^{2^3-1}(|x⟩ \\otimes |f(x)⟩)$.\n",
    "</center>\n",
    "Expending this:\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}(|000⟩ \\otimes |f(000)⟩$ + $|001⟩ \\otimes |f(001)⟩$ + $|010⟩ \\otimes |f(010)⟩$ + $|101⟩ \\otimes |f(101)⟩$ + $|110⟩ \\otimes |f(110)⟩$ + $|111⟩ \\otimes |f(111)⟩)$.\n",
    "</center>\n",
    "Apply H gates on the first three qubits again:\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}(\\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(000)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(001)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(010)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(011)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(100)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(101)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}+\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(110)⟩$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left( \\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\left(\\frac{|0⟩}{\\sqrt{2}}-\\frac{|1⟩}{\\sqrt{2}}\\right) \\otimes |f(111)⟩)$.\n",
    "</center>\n",
    "\n",
    "\n",
    "Expanding:\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}(\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(000)⟩ +|001⟩ \\otimes |f(000)⟩ + |010⟩ \\otimes |f(000)⟩ +|011⟩ \\otimes |f(000)⟩ + |100⟩ \\otimes |f(000)⟩ +|101⟩ \\otimes |f(000)⟩ + |110⟩ \\otimes |f(000)⟩ + |111⟩ \\otimes |f(000)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(001)⟩ - |001⟩ \\otimes |f(001)⟩ + |010⟩ \\otimes |f(001)⟩ - |011⟩ \\otimes |f(001)⟩ + |100⟩  \\otimes |f(001)⟩ - |101⟩ \\otimes |f(001)⟩ + |110⟩ \\otimes |f(001)⟩ - |111⟩ \\otimes |f(001)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(010)⟩ +|001⟩ \\otimes |f(010)⟩ - |010⟩ \\otimes |f(010)⟩ - |011⟩ \\otimes |f(010)⟩ + |100⟩  \\otimes |f(010)⟩ +|101⟩ \\otimes |f(010)⟩ - |110⟩ \\otimes |f(010)⟩ - |111⟩ \\otimes |f(010)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(011)⟩ - |001⟩ \\otimes |f(011)⟩ - |010⟩ \\otimes |f(011)⟩ +|011⟩ \\otimes |f(011)⟩ + |100⟩  \\otimes |f(011)⟩ - |101⟩ \\otimes |f(011)⟩ - |110⟩ \\otimes |f(011)⟩ + |111⟩ \\otimes |f(011)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(100)⟩ +|001⟩ \\otimes |f(100)⟩ + |010⟩  \\otimes |f(100)⟩ +|011⟩ \\otimes |f(100)⟩ - |100⟩ \\otimes |f(100)⟩ - |101⟩ \\otimes |f(100)⟩ - |110⟩ \\otimes |f(100)⟩ + |111⟩ \\otimes |f(100)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(101)⟩ - |001⟩ \\otimes |f(101)⟩ + |010⟩  \\otimes |f(101)⟩ - |011⟩ \\otimes |f(101)⟩ - |100⟩ \\otimes |f(101)⟩ + |101⟩ \\otimes |f(101)⟩ - |110⟩ \\otimes |f(101)⟩ + |111⟩ \\otimes |f(101)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(110)⟩ + |001⟩ \\otimes |f(110)⟩ - |010⟩  \\otimes |f(110)⟩ - |011⟩ \\otimes |f(110)⟩ - |100⟩ \\otimes |f(110)⟩ - |101⟩ \\otimes |f(110)⟩ + |110⟩ \\otimes |f(110)⟩ + |111⟩ \\otimes |f(110)⟩)\\right)$\n",
    "</center>\n",
    "<center>\n",
    "$+\\left( \\frac{1}{\\sqrt{2^3}} (|000⟩ \\otimes |f(111)⟩ - |001⟩ \\otimes |f(111)⟩ - |010⟩  \\otimes |f(111)⟩ + |011⟩ \\otimes |f(111)⟩ - |100⟩ \\otimes |f(111)⟩ + |101⟩ \\otimes |f(111)⟩ + |110⟩ \\otimes |f(111)⟩ - |111⟩ \\otimes |f(111)⟩)\\right)$\n",
    "</center>\n",
    "\n",
    "\n",
    "Refactoring as:\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}($\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ + |f(001)⟩ + |f(010)⟩ + |f(011)⟩ + |f(100)⟩ + |f(101)⟩ + |f(011)⟩ + |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ - |f(001)⟩ + |f(010)⟩ - |f(011)⟩ + |f(100)⟩ - |f(101)⟩ + |f(011)⟩ - |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ + |f(001)⟩ - |f(010)⟩ + |f(011)⟩ + |f(100)⟩ + |f(101)⟩ - |f(011)⟩ - |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ - |f(001)⟩ - |f(010)⟩ + |f(011)⟩ + |f(100)⟩ - |f(101)⟩ - |f(011)⟩ + |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ + |f(001)⟩ + |f(010)⟩ + |f(011)⟩ - |f(100)⟩ - |f(101)⟩ - |f(011)⟩ - |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ - |f(001)⟩ + |f(010)⟩ - |f(011)⟩ - |f(100)⟩ + |f(101)⟩ - |f(011)⟩ + |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ + |f(001)⟩ - |f(010)⟩ - |f(011)⟩ - |f(100)⟩ - |f(101)⟩ + |f(011)⟩ + |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$\\frac{1}{\\sqrt{2^3}}|000⟩ \\otimes |f(000)⟩ - |f(001)⟩ - |f(010)⟩ + |f(011)⟩ - |f(100)⟩ + |f(101)⟩ + |f(011)⟩ - |f(111)⟩)$\n",
    "</center>\n",
    "<center>\n",
    "$)$.\n",
    "</center>\n",
    "\n",
    "Which can be written as:\n",
    "<center>\n",
    "$\\sum_{y=0}^{2^3-1}(|y⟩ \\otimes \\left[ \\frac{1}{2^3}\\sum_{x=0}^{2^3-1}(-1)^{x.y}|f(x)⟩ \\right] )$,\n",
    "</center>\n",
    "where $x.y$ = $x1.y1$ + $x2.y2$ + $x3.y3$. Also note that $a\\oplus b\\oplus c \\oplus d$ = (a + b + c + d)%2 ($a$ and $b$ are bits) and (-1)$^{x \\oplus y}$ = (-1)$^x$(-1)$^y$ if $x$ and $y$ are bits.\n",
    "\n",
    "Now, let's calculate the probability for some state $y$:\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{x=0}^{2^3-1} (-1)^{x.y} |f(x)⟩\\right| \\right|^2$.\n",
    "</center>\n",
    "Note, if the state of a system is $a0|000⟩$ + $a1|001⟩$ + $a2|100⟩$ + $a3|101⟩$, it can be written as\n",
    "<center>\n",
    "$|0⟩(a0|00⟩$ + $a1|01⟩$ + $a2|00⟩$ + $a3|01⟩)$\n",
    "</center>\n",
    "Consider the case where $s$ = 000. The above expression becomes (for example if $U_f$ is a function $f(x)$ = $x$):\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{x=0}^{2^3-1} (-1)^{x.y} |x⟩\\right| \\right|^2$\n",
    "</center>\n",
    "<center>\n",
    "$= \\left| \\left| \\frac{1}{2^3} (-1)^{x.y} |000⟩ +  \\frac{1}{2^3} (-1)^{x.y} |001⟩ + \\frac{1}{2^3} (-1)^{x.y} |010⟩ + \\frac{1}{2^3} (-1)^{x.y} |011⟩ + \\frac{1}{2^3} (-1)^{x.y} |100⟩ + \\frac{1}{2^3} (-1)^{x.y} |101⟩ + \\frac{1}{2^3} (-1)^{x.y} |110⟩ + \\frac{1}{2^3} (-1)^{x.y} |111⟩ + \\right| \\right|^2$ .\n",
    "</center>\n",
    "\n",
    "The total probability of this subspace will be:\n",
    "<center>\n",
    "$(\\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2 + \\frac{1}{2^3} (-1)^{x.y})^2$,\n",
    "</center>\n",
    "which is\n",
    "<center>\n",
    "$2^3\\frac{1}{2^6}=\\frac{1}{2^3}$\n",
    "</center>\n",
    "(for the generic case, it is $\\frac{1}{2^n}$). The total probability will be the same even if we don't assume the function is $f(x) = x$, as long it is a 1-to-1 function, because only the order changes in that case\n",
    "but not the final sum. Hence, for $s$ = 000 , all the states are equally probable when we measure the first three qubits.\n",
    "\n",
    "<center>\n",
    "Consider the case when $s$ $\\neq$ 000. Let's rewrite the probability:\n",
    "</center>\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{x=0}^{2^3-1} (-1)^{x.y} |f(x)⟩\\right| \\right|^2$ .\n",
    "</center>\n",
    "This can be written as\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{z \\in A} (((-1)^{x1.y} + (-1)^{x2.y}) |z⟩)\\right| \\right|^2$\n",
    "</center>\n",
    "with $A$ defined as the range of the function $f$. It is 2-to-1 function and each state is repeated\n",
    "twice for two different inputs.\n",
    "\n",
    "This can be written as (because $x2 = x1 \\oplus s$; since $s = x1 \\oplus x2$ ) :\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{z \\in A} (((-1)^{x1.y} + (-1)^{(x1 \\oplus s).y}) |z⟩)\\right| \\right|^2$ .\n",
    "</center>\n",
    "which becomes\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{z \\in A} ((-1)^{x1.y} (1 + (-1)^{y.s}) |z⟩)\\right| \\right|^2$ .\n",
    "</center>\n",
    "If $y.s$ is an odd number, the above expression becomes 0. This means that, if we measure the first three qubits, we will never get a value $y$, such that $y.s$ is odd. If $y.s$ is even, then the above expression becomes:\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^3} \\sum_{z \\in A} ((-1)^{x1.y} (2) |z⟩)\\right| \\right|^2$ ,\n",
    "</center>\n",
    "which is\n",
    "<center>\n",
    "$\\left| \\left| \\frac{1}{2^{3-1}} \\sum_{z \\in A} ((-1)^{x1.y} |z⟩)\\right| \\right|^2$ .\n",
    "</center>\n",
    "It can be written as\n",
    "<center>\n",
    "$2^{3-1} (\\frac{1}{2^{3-1}})^2 = \\frac{1}{2^{3-1}} $\n",
    "</center>\n",
    "(for the generic case, it is $\\frac{1}{2^{n-1}}$). Because we have only half of the states to sum; each state $z$ is repeated twice. This means that if we measure the first three qubits, we will get only those states where $y.s$ = even, with equal probability.\n",
    "</div>\n",
    "\n",
    "\n",
    "\n",
    "Let's reiterate our findings:\n",
    "\n",
    "1. When $s$ = 000 , if we measure the first three qubits, we will get all the states with equal probability.\n",
    "2. When $s$ = 000 , if we measure the first three qubits, we will never get a state that satisfies $y.s$ = odd and we can get any state that satisfies $y.s$ = even with equal probability.\n",
    "\n",
    "\n",
    "Let's say we execute the circuit (for $n$ = 4) and get the following output when we measured the first four qubits:\n",
    "\n",
    "<center>\n",
    "$y$ = 1011.\n",
    "</center>\n",
    "\n",
    "It means that this $y$ satisfies $y.s$ = even. This means\n",
    "\n",
    "<center>\n",
    "$y0.s0 \\oplus y1.s1 \\oplus y2.s2 \\oplus y3.s3 = 0$,\n",
    "</center>\n",
    "\n",
    "which means\n",
    "\n",
    "<center>\n",
    "$1.s0 \\oplus 0.s1 \\oplus 1.s2 \\oplus 1.s3 = 0$.\n",
    "</center>\n",
    "\n",
    "If we execute the circuit again and get the following output:\n",
    "\n",
    "<center>\n",
    "$y$ = 1110.\n",
    "</center>\n",
    "\n",
    "It means\n",
    "\n",
    "<center>\n",
    "$1.s0 \\oplus 1.s1 \\oplus 1.s2 \\oplus 0.s3 = 0$.\n",
    "</center>\n",
    "\n",
    "If we execute the circuit again and we get\n",
    "\n",
    "<center>\n",
    "$y$ = 0110.\n",
    "</center>\n",
    "\n",
    "It means\n",
    "\n",
    "<center>\n",
    "$0.s0 \\oplus 1.s1 \\oplus 1.s2 \\oplus 0.s3 = 0$.\n",
    "</center>\n",
    "\n",
    "By solving these three equations we can find the value of s to be 0111 and 0000.\n",
    "\n",
    "Now, we should try to execute the black box for 0000 and 0111 (i.e. 0000 $\\oplus$ 01 11), if we get the same output then we can safely say that $s$ = 0111. If the output is not the same, then we can conclude\n",
    "that the black box represents and 1 to 1 function and $s$ = 0000.\n",
    "\n",
    "Note that though we have a 4-variable problem, we needed only three simultaneous equations, because we know that $s$ = 0000 will always be a solution of those equations. Another important note is that, we should always need linearly independent equations to get a solution. For example, if we get the following three measurements:\n",
    "\n",
    "<center>\n",
    "1011 <br>\n",
    "\n",
    "1110 <br>\n",
    "\n",
    "0101 <br>\n",
    "</center>\n",
    "\n",
    "the last value is nothing but 1011 $\\oplus$ 1110. Such measurements are useless because they will not help in finding a unique solution. So, if we have an $n$-bit problem, we need $n$ - 1 linearly independent equations\n",
    "to solve them. We need to execute the circuit several times until we get $n$ - 1 linearly independent values while we measure the $n$ qubits. 0000 is linearly dependent on every value, so it is also not useful.\n",
    "\n",
    "Let's see in more depth with an example on how to identify linearly dependent values. Say we have the following values so far:\n",
    "\n",
    "<center>\n",
    "1011\n",
    "\n",
    "1110\n",
    "\n",
    "0110\n",
    "</center>\n",
    "\n",
    "The following is the list of linearly dependent values:\n",
    "\n",
    "Given values:\n",
    "\n",
    "<center>\n",
    "1011\n",
    "\n",
    "1110\n",
    "\n",
    "0110\n",
    "</center>\n",
    "\n",
    "XOR of any two values:\n",
    "\n",
    "<center>\n",
    "0101\n",
    "\n",
    "1101\n",
    "\n",
    "1000\n",
    "</center>\n",
    "\n",
    "XOR of any three values:\n",
    "\n",
    "<center>\n",
    "0011\n",
    "</center>\n",
    "\n",
    "Also, 0000 is linearly dependent on any value. In total we have 8 values. The generic formula is that if we have $n$ linearly independent values, then we can make $2^n$ linearly dependent values out of them.\n",
    "\n",
    "If we have an $n$-qubit system and we have executed the black box $n$ - 1 times, let's calculate the probability that all of them are linearly independent (consider the case where $s \\neq 0^n$). In the first iteration\n",
    "we can get any value except $0^n$; because it is linearly dependent on all the values. The probability of getting $0^n$ is\n",
    "\n",
    "<center>\n",
    "$\\frac{1}{2^{n-1}}$ .\n",
    "</center>\n",
    "\n",
    "The probability of not getting it is\n",
    "\n",
    "<center>\n",
    "$1-\\frac{1}{2^{n-1}}$ .\n",
    "</center>\n",
    "\n",
    "Say we completed $m$ - 1 iterations and we have that many linearly independent values. We can make $2^{m-1}$ linearly dependent values out of them so the probability that the next value will be linearly dependent will be $2^{m-1}/2^{n-1}$. After $n$ - 1 iterations, the probability that all of them are linearly independent is\n",
    "\n",
    "<center>\n",
    "Pr = $\\left( 1- \\frac{1}{2^{n-1}} \\right) \\left( 1- \\frac{2}{2^{n-1}} \\right)...\\left( 1- \\frac{2^{n-2}}{2^{n-1}} \\right)$ .\n",
    "</center>\n",
    "\n",
    "We need some advanced knowledge of a series called $q$-series to find this value. The reader should feel\n",
    "free to explore. It is more of a mathematical problem than a quantum computing problem. The output\n",
    "will be around 0.288 (i.e. > ¼).\n",
    "\n",
    "\n",
    "Using C# code to help evaluate:\n",
    "\n",
    "<img src=\"img/5-sac.png\" style=\"width: 90%;\">\n",
    "\n",
    "<p style=\"font-family:courier\"><font color=\"blue\">static void</font> Main(<font color=\"blue\">string</font>[] args)<br>\n",
    "{<br>\n",
    "<br>\n",
    "    <font color=\"blue\">double</font> n = 1000;<br>\n",
    "    <font color=\"blue\">double</font> product = 1.0;<br>\n",
    "    <font color=\"blue\">for</font> (<font color=\"blue\">double</font> i = 0.0; i < n-1.0; i++)<br>\n",
    "    {<br>\n",
    "        <font color=\"blue\">double</font> tempProduct = 1.0;<br>\n",
    "        tempProduct = 1.0 - (Math.Pow(2.0, i) / Math.Pow(2.0, n-1.0));<br>\n",
    "        product = product * tempProduct;<br>\n",
    "        Console.WriteLine(product);<br>\n",
    "    }<br>\n",
    "    Console.WriteLine(<font color=\"red\">$\\$ $\"\\nfinal:</font> {product}\");<br>\n",
    "    Console.WriteLine(<font color=\"red\">\"Done\"</font>);<br>\n",
    "    Console.ReadLine();<br>\n",
    "}</p>\n",
    "\n",
    "\n",
    "The probability of success above is ½.\n",
    "\n",
    "For the remaining terms:\n",
    "\n",
    "= $\\left( 1- \\frac{1}{2^{n-1}} \\right) \\left( 1- \\frac{2}{2^{n-1}} \\right)...\\left( 1- \\frac{2^{n-3}}{2^{n-1}} \\right)$\n",
    "\n",
    "= $\\left( 1- \\frac{1}{2^{n-1}} \\right) \\left( 1- \\frac{2}{2^{n-1}} \\right)... \\left( 1- \\frac{2^{n-4}}{2^{n-1}} \\right) \\left( 1- \\frac{2^{n-3}}{2^{n-1}} \\right)$\n",
    "\n",
    "Reversing the order:\n",
    "\n",
    "$\\left( 1- \\frac{2^{n-3}}{2^{n-1}} \\right) \\left( 1- \\frac{2^{n-4}}{2^{n-1}} \\right) \\left( 1- \\frac{2}{2^{n-1}} \\right) \\left( 1- \\frac{1}{2^{n-1}} \\right)$\n",
    "\n",
    "Because $1-a-b \\leq (1-a)(1-b)$, if $0 \\leq a,b \\leq 1$, we can write as follows:\n",
    "\n",
    "Probability $\\geq \\left( 1- \\frac{2^{n-3}}{2^{n-1}} - \\frac{2^{n-4}}{2^{n-1}} ... - \\frac{2}{2^{n-1}} - \\frac{1}{2^{n-1}} \\right)$\n",
    "\n",
    "$\\geq \\left( 1 - \\left( \\frac{1}{4} \\right) (1 + \\frac {1}{2} + \\frac{1}{4} ...) \\right)$\n",
    "\n",
    "$\\geq 1 - \\left( \\frac{1}{4} \\right) (2)$(because the maximum value of the above series is 2)\n",
    "\n",
    "$\\geq \\left( \\frac{1}{2}\\right)$\n",
    "\n",
    "So, multiplying this with the ½ we had in the last step gives\n",
    "\n",
    "<center>\n",
    "Probability $\\geq \\left( \\frac{1}{4}\\right)$.\n",
    "</center>\n",
    "\n",
    "Though this probability is slightly less than the accurate one culculation using $q$-series, it was easier to\n",
    "prove.\n",
    "\n",
    "¼ might seem like a small probability but bear in mind that this is the probability after performing\n",
    "only $n$ - 1 iterations (increasing linearly with the number of qubits), whereas classically we might have to do about 2 $^\\frac{n}{2}$(increasing exponentially with the number of qubits) iterations for the solution. Performing the iterations a few times or even a few multiple times more than $n$ - 1 will yield a solution with very high probability.\n",
    "\n",
    "### Q# exercise: Simon's algorithm\n <a id='#qex'></a>",
    "\n",
    "1. Go to $\\href{https://garagein.visualstudio.com/_git/QuantumComputingSamples?path=%2FQuantumComputingViaQSharpSolution&version=GBmaster}{QuantumComputingViaQSharpSolution}$ introduced in session 1.1.\n",
    "2. Open 27_Demo Simon's Algorithm Operation.qs in Visual Studio (Code).\n",
    "3. The exercise uses $n$ = 4 as an example. Lines 8-43 set up the Simon's algorithm circuit as introduced in the session.\n",
    "<img src=\"img/5-ex3.png\" style=\"width: 90%;\">\n",
    "4. Example black boxes 0000 and 1010 are defined in lines 113-198 following the below circuits.\n",
    "<img src=\"img/5-ex41.png\" style=\"width: 90%;\">\n",
    "<img src=\"img/5-ex42.png\" style=\"width: 90%;\">\n",
    "5. Run the script via $dotnet$ $run$. You'll find the 20 input iterations and testing results for 0000, 1010, 1110 and 0100.\n",
    "6. More Simon's algorithm exercise can be found in $\\href{https://github.com/Microsoft/QuantumKatas}{Quantum Katas}$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
